package leetcode_1_20;

import java.util.Arrays;

public class threeSumClosest_16 {
    /**
     * 思路类似三数之和
     * 先从小到大排序
     * 如果遍历到正数后，还不是最接近的，就可以直接返回了
     * 因为后边的数只会更大
     * 保留去重操作
     * 太慢了有点
     * @param nums
     * @param target
     * @return
     */
    public static int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        //将数组进行排序
        Arrays.sort(nums);
        int lastnums1=Integer.MIN_VALUE,
                lastnums2=Integer.MIN_VALUE,
                lastnums3=Integer.MIN_VALUE;
        int longest=nums[0]+nums[1]+nums[2];        //距离目标最近的数字
        for(int i=0;  i < len -2; i++) {
            int a=nums[i];
            if(i != 0
                    &&a >= 0&& nums[i+1] >=0   //当三个数都大于0 往后遍历单向递增
                    &&(a+nums[i+1]+nums[i+2])>longest        //说明longest三个数字不是都在之前的数字中，就不能使用该条件判定
                    && (Math.abs(a+nums[i+1]+nums[i+2] - target) >Math.abs( longest -target)))
                // 判断此时差值是否更大，是就直接返回longest
                // nums[i] > 0 时，说明后边之和肯定都大于0
                return longest;
            //顺序遍历
            if( lastnums1 != Integer.MIN_VALUE && a == lastnums1)             //数字与上一个数字相同直接跳过
                continue;
            for (int t = i + 1; t < len-1; t++) {
                int b=nums[t];
                if( lastnums2 != Integer.MIN_VALUE && nums[t] == lastnums2)             //数字与上一个数字相同直接跳过
                    continue;
                //确定两个数字后，看剩下的是否存在符合条件的第三个数
                for (int j = t + 1; j < len; j++) {
                    int c=nums[j],
                        sum=a+b+c;
                    if( lastnums3 != Integer.MIN_VALUE && c == lastnums3)             //数字与上一个数字相同直接跳过
                        continue;
                    //当c 为正数时，以后遍历只会更大
                    if (     j != i + 2                   //第一个不做判断
                            && c >= 0
                            && (Math.abs(sum - target) >Math.abs( longest -target))){
                        break;//第二个数
                        }
                    if( sum == target) return target;
                    if( Math.abs(sum - target) < Math.abs( longest -target)){         //更接近就赋值给longest
                        longest = sum;
                    }
                    lastnums3=nums[t];
                }
                    lastnums2=nums[t];
                    lastnums3=Integer.MIN_VALUE;
            }
            lastnums1=nums[i];
            lastnums2=Integer.MIN_VALUE;
            lastnums3=Integer.MIN_VALUE;
        }
        return longest;
    }

    /**
     * 排序双指针
     * @param nums
     * @param target
     * @return
     */
    public static int threeSumClosest2(int[] nums, int target) {
    int n=nums.length;
    Arrays.sort(nums);
    int closeNum=nums[0]+nums[1]+nums[2];
    for(int i=0;i<n;++i){
        int left=i+1,right=n-1;
        while(left<right){
            int sum=nums[i]+nums[left]+nums[right];
            if(Math.abs(target-sum)<Math.abs(target-closeNum)){
                closeNum=sum;
            }else if(sum>target){
                right--;
            }else if(sum<target){
                left++;
            }else{
                return target;
            }
        }
    }
    return closeNum;
    }
}
